Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Аналіз сортування алгоритму методом прямого вибирання

Інформація про навчальний заклад

ВУЗ:
Вінницькій національний технічний університет
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
ФІТКІ
Кафедра:
КН

Інформація про роботу

Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
КН 2
Варіант:
13

Частина тексту файла

Міністерство освіти і науки України Вінницький національний технічний університет Факультет інформаційних технологій і комп’ютерної інженерії Кафедра комп’ютерних наук Лабораторна робота №2 З дисципліни: Теорія алгоритмів Тема: «Аналіз сортування алгоритму методом прямого вибирання» Вінниця, 2017 Аналіз сортування алгоритму методом прямого вибирання Мета: проаналізувати складність алгоритму методом прямого вибирання, практично та аналітично. Навчитись оцінювати асимптотичну складність алгоритму. Ідея алгоритму: Серед n елементів масиву вибирається найменший. Він міняється місцями з першим елементом a1. Далі цей процес повторюється із рештою n - 1 елементами, n – 2 елементами і т. д. доти, поки не залишиться один, найбільший елемент. Такий алгоритм, у певному смислі, протилежний алгоритму сортування вставками. В останньому випадку на кожному кроці розглядається тільки один черговий елемент вихідної послідовності та всі елементи готової послідовності, серед яких відшуковується точка вставки; при прямому виборі для пошуку одного елементу з найменшим ключем проглядаються всі елементи вихідної послідовності і знайдений розташовується як черговий елемент у готову послідовність. Час роботи алгоритму: Як і у випадку сортування вставками, склавши внески всіх рядків отримаємо час виконання в загальному випадку: Відсортований масив: Цей випадок є найсприятливіший, оскільки не виконуються блоки 6 і 7, а отже час виконання буде найменшим. Відсортований у зворотному напрямку масив: Цей випадок є найнесприятливіший, оскільки кожен елемент масиву потрібно переміщати, а отже час виконання буде найбільший. Псевдокод алгоритму сортування прямим вибором: Блок-схема алгоритму сортування прямим вибором: Код програми: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Diagnostics; namespace _1234 { class Program { static void Main(string[] args){ // Створення масиву// Random zap = new Random();//для отримання випадкових цілих чисел Console.WriteLine("Введiть кiлькiсть елементiв масива:"); int a = Convert.ToInt32(Console.ReadLine());//конвертуєм змінну а в int Stopwatch watch0 = new Stopwatch(); watch0.Start(); int[] arr1 = new int[a]; Console.WriteLine("Невідсортований массив:"); //створюєм масив for (int q = 0; q < a; q++) { arr1[q] = zap.Next(1, 100); Console.Write(arr1[q] + " "); } watch0.Stop(); Console.WriteLine("\nЧас виконання програми в мілесекундах : " + watch0.ElapsedMilliseconds + "mc.\r\n"); //Сортування масиву// Stopwatch watch = new Stopwatch(); //для визначення часу виконання масиву watch.Start(); int min = 0, temp = 0; for (int i = 0; i < a - 1; i++) //сортуємо масив { min = i; for (int j = i + 1; j < a; j++) { if (arr1[j] < arr1[min]) { min = j; } } temp = arr1[i]; arr1[i] = arr1[min]; arr1[min] = temp; } Console.WriteLine("\nВiдсортований масив"); for (int i = 0; i < arr1.Length; i++) { Console.Write(arr1[i] + " "); //виводимо масив } watch.Stop(); Console.WriteLine("\nЧас виконання програми в мілесекундах : " + watch.ElapsedMilliseconds + "mc.\r\n"); //Сортування масиву у зворотньому напрямку// Stopwatch watch1 = new Stopwatch(); //для визначення часу виконання масиву watch1.Start(); int min1 = 0, temp1 = 0; for (int i = 0; i < a - 1; i++) //сортуємо масив ...
Антиботан аватар за замовчуванням

24.10.2018 17:10

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини